package leetcode.dfs;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

//116. 填充每个节点的下一个右侧节点指针
//117. 填充每个节点的下一个右侧节点指针 II
//俩题的区别就是 第一个题是一个完全二叉树 第二个是一个普通二叉树
public class Connect {
    public static void main(String[] args) {

    }


    // 层次遍历
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);//根节点入队
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 从队首取出元素
                Node temp = queue.poll();

                //如果队列中只有一个元素,那么他就没有兄弟结点
                if (i != size - 1) {
                    temp.next = queue.peek();
                } else {
                    temp.next = null;
                }
                if (temp.left != null) {
                    //因为是完全二叉树，如果左边不为空，右边一定不为空
                    queue.offer(temp.left);
                    queue.offer(temp.right);
                }
            }
        }
        return root;
    }

    //递归
    public Node connect12(Node root) {
        if (root == null) {
            return null;
        }
        if (root.left != null) {
            root.left.next = root.right;
            root.right.next = root.next != null ? root.right.next = root.next.left : null;
            connect(root.left);
            connect(root.right);
        }
        return root;
    }


    //BFS
    public Node connect2(Node root) {
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node temp = queue.poll();
                //如果队列中只有一个元素,那么他就没有兄弟结点
                if (i != size - 1) {
                    temp.next = queue.peek();
                } else {
                    temp.next = null;
                }
                if (temp.left != null) {

                    queue.offer(temp.left);
                    if (temp.right != null) {
                        queue.offer(temp.right);
                    }
                } else {
                    if (temp.right != null) {
                        queue.offer(temp.right);
                    }
                }
            }
        }
        return root;
    }

    //BFS优化---结合单链表
    public Node connect21(Node root) {
        if (root == null) {
            return null;
        }
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候，为了方便操作在下一
            //层前面添加一个哑结点（注意这里是访问
            //当前层的节点，然后把下一层的节点串起来）
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            while (cur != null) {
                if (cur.left != null) {
                    pre.next = cur.left;
                    pre = pre.next;
                }
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                cur = cur.next;
            }
            cur = dummy.next;
        }
        return root;
    }

    Map<Integer, Node> map = new HashMap<>();

    // 二战
    public Node connectP(Node root) {
        dfs(root, 0);
        return root;
    }

    private void dfs(Node node, int depth) {
        if (node == null) {
            return;
        }
        if (map.containsKey(depth)) {
            map.get(depth).next = node;
        }
        map.put(depth, node);
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);

    }


}


class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
